Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Знаходження шляхів графа

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики

Інформація про роботу

Рік:
2009
Тип роботи:
Лабораторна робота
Предмет:
Математика
Група:
ПМ-21

Частина тексту файла

Міністерство освіти та науки України Національний університет «Львівська політехніка» Інститут прикладної математики та фундаментальних наук Кафедра прикладної математики Лабораторна робота №2 «Знаходження шляхів графа» Тема: знаходження шляхів в графі. Мета: дати можливість студентам детальніше в практичному відношенні засвоїти тему по знаходженню різних шляхів в графах за допомогою засобів ЕОМ. Теоретичні відомості: Транспортна сітка  є сукупністю двох об’єктів 1) зв’язного графа  з такими властивостями: в графі  відсутні петлі в графі  існує одна і тільки одна вершина  така, що множина . 2) цілочисельної невід’ємної функції , заданої на множині  дуг графа . Вершина  називається входом сітки, вершина – виходом. Значення  на дузі  називається пропускною здатністю дуги. 3) Нехай  – множина дуг, що заходять у вершину , а  – множина дуг, які виходять із вершини . Цілочисельна невід’ємна функція , задана на множині  дуг графа  називається потоком, якщо вона задовольняє таким умовам: а)  б)  Із а) випливає, що . Величина  називається величиною потоку  і позначається . Алгоритм Форда – Фалкерсона (для знаходження потоку найбільшої величини). 10 Перенумерувати довільним чином вершини сітки  відмінні від  і . 20 Побудувати довільний потік  на транспортній сітці  (наприклад покласти ). 30 Розглянути шляхи, що з’єднують вхід сітки  з виходом , якщо потік  повний – перейти до пункту 40. Іншому випадку розглянути шлях , що з’єднує  з , всі дуги якого ненасичені. Побудувати новий потік :  Повторити увесь процес до одержання повного потоку . Присвоїти цілочисельні мітки вершинам сітки  і знаки (+) або (-) дугам по правилах: а) входу  присвоїти мітку 0, б) якщо вершина  одержала деяку мітку, а  – ще не помічена вершина, то вершині , такій, що , присвоїти мітку , а дузі  знак (+); вершині , такій, що , присвоїти мітку , а дузі  знак (-); інші вершини і дуги мітки і знаку не отримують. в) повторяти процес, описаний в 40(б) до тих пір, поки не виявиться, що присвоїти мітку або знак новій непоміченій вершині або дузі неможливо. Якщо в результаті процесу вершина  не одержить мітки, то потік володіє найбільшою величиною. В іншому випадку перейти до пункту г). г) розглянути послідовність відмічених вершин , кожна з яких має мітку, що дорівнює номеру наступної вершини, і послідовність дуг  (необов’язково шлях), що з’єднує послідовні вершини із . Побудувати новий потік  таким чином:  і перейти до п.4. Завдання: Скласти програму знаходження максимального потоку у сітці заданої таким чином: 01 12 23 15 05 06 76 57 68 78 37 34 56 48 49 89 4z 9z  10 11 8 7 8 9 9 11 10 4 5 17 18 20 21 19 20 23  (Варіант 13) Код програми(С++): #include<stdio.h> #include<conio.h> #define n 11 int C[n][n], N[n], i, j, F[n][n], T[n][n], p; int Vvid(int &v); void First(int v); void Second(int v); int Potik(int v); void main() { int v; printf("Algorutm Forda-Falkirsona."); if (Vvid(v)) { Second(v); printf("\nMaksumal'nuj potik transportnoji merezhi = %d\n",Potik(v)); } getch(); } int Vvid(int &v) { int i, j, k; char *fname = "Potik.txt"; FILE *F; if((F = fopen(fname, "r")) == NULL) { puts("File not found"); return 0; } fscanf(F, "%d",&v); if(v > n) v = n; while(!feof(F)) { fscanf(F, "%d %d %d", &i, &j, &k); C[i][j] = k; } fclose(F); for(i = 0; i < n; i++) { puts("\n"); for(j = 0; j < n; j++) if (C[i][j] / 10 == 0) printf("%d ", C[i][j]); else printf("%d ", C[i][j]); } return 1; } void First(int v) { for(int i = 1; i < v; i++) N[i] = -1; N[0] = 0; for(p = 1; p; ) { p = 0; int i, j; for(i = 0; i < v; i++) if(N[i] == -1) continue; else for(j = 0; j < v; j++) { if(N[j] != -1) continue; if(C[i][j] && (F[i][j] < C[i][j])) { N[j] = i; T[i][j] = 1; p = 1; } if(C[j][i] && F[j][i]) { N[j] = i; T[j][i] = -1; p =...
Антиботан аватар за замовчуванням

01.01.1970 03:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини